//https://leetcode.cn/problems/palindromic-substrings/
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        //dp[i][j]:表示字符串以i为起始位置,j为结束位置的子串是否是回文子串 (i<=j)
        vector<vector<bool>> dp(n,vector<bool>(n)); 
        int res = 0;
        for(int i = n-1;i>=0;i--) //从i为起始位置
        {
            //for(int j = i;j<n;j++)也可以
            for(int j = n-1;j>=i;j--) //以j为结束位置  i<=j<= n-1 
            {
                //dp表的内容默认就是false，所以s[i] != s[j]不需要考虑
                if(s[i] == s[j])   
                    dp[i][j] = i + 1 < j ?dp[i+1][j-1] :true;
                if(dp[i][j]) 
                    res++;
            }
        }
        return res;
    }
};


//https://leetcode.cn/problems/palindrome-partitioning-iv/
class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        //dp[i][j]:以i位置为起点，j位置为终点的子串，是否是回文子串
        vector<vector<bool>> dp(n,vector<bool>(n)); 
        //1.填写dp表，保存所有子串是否回文的信息
        for(int i = n - 1; i >= 0;i--)
        {
            for(int j = i;j < n;j++)
            {
                if(s[i]  == s[j])
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] :true;
            }
        }
        //2.枚举第二个子串的起始位置i和结束位置j  划分为3个子串：[0,i-1][i,j][j+1,n-1]
        //要保证第一个子串和第三个子串必须要有一个字符  1<=i<=n-2     i<=j<=n-2
        for(int i = 1;i<n-1;i++)
        {
            for(int j = i;j<n-1;j++) 
            {
                //如果三个子串都是回文子串，那么就可也将s分割成三个回文子串
                if(dp[0][i-1] && dp[i][j] && dp[j+1][n-1])
                    return true;
            }
        }
        return false;
    }
};